import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-08-16
 * Time: 11:25
 */
public class Test {

    //leetcode 283 移动零
    public void moveZeroes(int[] nums) {
        for(int slow = -1,fast = 0; fast < nums.length; fast++) {
            if(nums[fast] != 0) {
                int tmp = nums[++slow];
                nums[slow] = nums[fast];
                nums[fast] = tmp;
            }
        }
    }
    //leetcode 1089 复写零
    public void duplicateZeros(int[] arr) {
        //1.先找到最后一个无需复写的数
        int slow = 0;
        int fast = -1;
        int n = arr.length;
        while(fast < n) {
            if(arr[slow] != 0) {
                fast++;
            }else {
                fast += 2;
            }
            if(fast >= n-1) break;
            slow++;
        }
        //2.调整边界
        if(fast == n) {
            arr[--fast] = 0;
            fast--;
            slow--;
        }
        while(slow >= 0) {
            if(arr[slow] != 0) {
                arr[fast--] = arr[slow];
            }else {
                arr[fast--] = 0;
                arr[fast--] = 0;
            }
            slow--;
        }
    }

    //leetcode 202 快乐数
    private int bitSum(int n) {
        int sum = 0;
        while(n != 0) {
            int tmp = n % 10;
            sum += tmp * tmp;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = bitSum(n);
        while(slow != fast) {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }

        return slow == 1;
    }

    //leetcode 11 盛最多水的容器
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int max = 0;
        while(left <= right) {
            int v = Math.min(height[left],height[right]) * (right - left);
            max = Math.max(max,v);
            if(height[left] < height[right]) left++;
            else right--;
        }

        return max;
    }

    //leetcode 611 有效三角形的个数
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ret = 0;
        for(int i = nums.length-1; i >= 2; i--) {
            int left = 0;
            int right = i-1;
            while(left <= right) {
                if(nums[left] + nums[right] > nums[i]) {
                    ret = ret + right - left;
                    right--;
                }else {
                    left++;
                }
            }
        }

        return ret;
    }

    //leetcode 剑指offer57 和为s的两个数字
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <= right) {
            int sum = nums[left] + nums[right];
            if(sum < target) {
                left++;
            }else if(sum > target) {
                right--;
            }else {
                return new int[]{nums[left],nums[right]};
            }
        }

        return new int[]{-1,-1};
    }
}
